/* *
* 时间复杂度为O(nlogn) 空间复杂度为O(n) 稳定
* 归并排序的基本思想是将待排序数组分成若干个子数组，每个子数组都是有序的，然后将这些子数组两两合并，直到合并成一个完整的有序数组。
* 归并排序的过程可以使用递归来实现。首先将数组一分为二，然后对左右两个子数组分别递归调用归并排序，直到每个子数组只有一个元素为止。
* 然后将两个有序的子数组合并成一个有序的数组，最终得到的数组就是完整的有序数组
* */
function mergeSort(arr) {
    const len = arr.length;
    if (len <= 1) return arr
    const mid = Math.floor(len / 2)
    const leftArr = mergeSort(arr.slice(0, mid))
    const rightArr = mergeSort(arr.slice(mid, len))
    arr = merge(leftArr,rightArr)
    return arr
}
function merge(left,right) {

    let i = 0
    let j = 0
    let res = []
    while (i < left.length && j < right.length) {
        if (left[i] <= right[j]) {
            res.push(left[i])
            i++
        }
        else {
            res.push(right[j])
            j++
        }
    }
    if (i < left.length) {
        return [...res, ...left.slice(i)];
    } else {
        return [...res, ...right.slice(j)];
    }
}
const arr = [5,2,6,1,7,2,10,8]
console.log(mergeSort(arr));
